package org.example.ch04;

import org.example.ch04.tree.ConstructTree;
import org.example.ch04.tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 *
 *给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。
 *
 */
public class BuildTree {
    private Map<Integer, Integer> indexMap;

    public static void main(String[] args) {

       int[] preorder = {3,9,20,15,7}, inorder = {9,3,15,20,7};

       BuildTree build = new BuildTree();
        TreeNode root = build.buildTree(preorder,inorder);
        //前序遍历打印信息
        ConstructTree.preOrder(root);

    }

    /**
     * 根据前序遍历和中序遍历，构造树
     * @param preorder
     * @param inorder
     * @return
     */
    public  TreeNode buildTree(int[] preorder,int[] inorder){
        int preLen = preorder.length;
        int inLen = inorder.length;

        Map<Integer,Integer> map = new HashMap<Integer,Integer>(inLen);
        int preLeft = 0;
        int preRight = preLen-1;
        int inLeft = 0;
        int inRight = inLen-1;
        for (int i = 0; i < inLen; i++) {
            //存储值和索引
            map.put(inorder[i],i);
        }

       return  mybuildTree(preorder,preLeft,preRight,inLeft,inRight,map);
    }

    /**
     * 递归函数构建树结构
     * @param preorder
     * @param preLeft
     * @param preRight
     * @param inLeft
     * @param inRight
     * @param map
     * @return
     */
    private TreeNode mybuildTree(int[] preorder,
                             int preLeft,
                             int preRight,
                             int inLeft,
                             int inRight,
                             Map<Integer, Integer> map) {
        //递归的终结条件
         if(preLeft>preRight || inLeft>inRight){
             return null;
         }
        //执行本层逻辑
        //获取根节点
        int rootValue = preorder[preLeft];
         //获取中序遍历的根节点索引
         int pIndex = map.get(rootValue);

        TreeNode root = new TreeNode(rootValue);
        //下探到下一层递归，传入主角
        root.left = mybuildTree(preorder,preLeft+1,pIndex-inLeft+preLeft,inLeft,pIndex-1,map);
        root.right = mybuildTree(preorder,pIndex-inLeft+preLeft+1,preRight,pIndex+1,inRight,map);
        //清理本层状态（包括返回值等）

        return root;
    }


}
